package Class029_异或;

//异或就是无进位相加
//异或的一些骚操作
//无符号右移就是最高位全部补0
//带符号右移就是用标志位来补。负数就全部补1，非负补0
public class EOR {
    public static void main(String[] args) {
        int a = 10,b = -39;
        System.out.println(getMax(a,b));
    }

    //a个白球b个黑球
    //每次拿两个球，放回1个，规则：
    //两个相同色的，则放回白
    //不同色，放回黑
    //问最后是黑球的概率是多少? 用a和b表示
    //这个和异或有啥关系?
    //根据异或的性质，0^n = n, n ^ n = 0. 并且符合交换律，a^b^c^d^.., 随便交换顺序
    //因为是无进位相加，当前位的结果并不会影响其他位
    //那么，把白球看成0, 黑球看成1
    //相同色产生白色 => 0 ^ 0 = 0, 1 ^ 1 = 0
    //不同色产生白色 => 1 ^ 0 = 1, 0 ^ 1 = 1
    //所以就是a个0，b个1开始异或: 0 ^ 1 ^ 1 ^ 0 ^ ....
    //根据交换律，等价于: (a个0异或) ^ (b个1异或) = b个1异或 => 只和黑球数量有关
    //当b为奇数，结果就是1，即黑球
    //当b为偶数，结果就是0，即白球
    public static void blackAndWhite(int a, int b) {
        if((b & 1) == 0) {
            System.out.println("白球");
        }else {
            System.out.println("黑球");
        }
    }

    //交换两个数
    //不过当i == j时，该操作会出错
    //根据异或的性质，arr[i]位置的数会被刷成0
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    //如何不通过比较(>,<,>=,<=,==)来返回两个数较大的那个?
    //只能通过两数之差 c = a - b 入手
    //如果c > 0, 说明a > b
    //无法用 > 号判断一个数是否 > 0...可通过位运算

    //num >>> 31 => 无符号右移31位后，符号位就到了最低位。此时 & 1 的结果如果是1，则说明num是负数
    //如果是0，则说明是非负数

    /**
     * @return if num < 0, return 0; if num >= 0, return 1
     */
    public static int getSign(int num) {
        return flip((num >>> 31) & 1);
    }

    /**
     * @param num either = 0 or = 1
     * @return flip num.
     */
    public static int flip(int num) {
        return num ^ 1;
    }

    //c = a - b
    //若a,b同号，并且c 非负
    //若a,b异号，且a 非负
    //认为a是较大的数
    //a,b同号且c非负是条件1
    public static int getMax(int a, int b) {
        int c = a - b;
        int signA = getSign(a);
        int signB = getSign(b);
        int signC = getSign(c);
        int diffAB = signA ^ signB; //a,b异号时，变量为1
        int sameAB = flip(diffAB); //a,b同号时，为1
        int returnA = (diffAB & signA) + (sameAB & signC);
        int returnB = flip(returnA);
        return a * returnA + b * returnB;
    }

    //寻找缺失的数字
    //数组的长度为n，有[0~n]需要填入，必然有一个缺失
    //如何找到
    //n ^ n = 0, n ^ 0 = n
    //a ^ b = c
    //a => eorNum, b => missingNumber, c => eorAll
    //b = a ^ c
    public static int missingNumber(int[] nums) {
        int eorNum = 0;
        int eorAll = 0;
        int N = nums.length;
        for(int i = 0; i < N; i++) {
            eorNum ^= nums[i];
            eorAll ^= i;
        }
        eorAll ^= N;
        return eorAll ^ eorNum;
    }

    //数组中有两个数只出现奇数次，其他出现偶数次，找出这两个数
    //要求: O(n) + O(1)
    public static int[] singleNumber(int[] nums) {
        int AXorB = 0;
        for(int i: nums) {
            AXorB ^= i;
        }
        int unique = AXorB & (-AXorB);
        int a = 0;
        for(int i: nums) {
            if((i & unique) == 0) {
                a ^= i;
            }
        }
        return new int[] {a, a ^ AXorB};
    }

    //数组中其他数都出现了m次，有一个数出现少于m次。找出这个数
    public static int singleNumber2(int[] nums, int m) {
        int[] record = new int[32];
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < 32; j++) {
                if((nums[i] & 1) != 0) {
                    record[j]++;
                    record[j] %= m;
                }
                nums[i] >>>= 1;
            }
        }
        int ans = 0;
        for(int i = 0; i < 32; i++) {
            if(record[i] != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}
